{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "############## PLEASE RUN THIS CELL FIRST! ###################\n",
    "\n",
    "# import everything and define a test runner function\n",
    "from importlib import reload\n",
    "from helper import run\n",
    "import block\n",
    "import ecc\n",
    "import helper\n",
    "import network\n",
    "import script\n",
    "import tx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from helper import hash256\n",
    "hash0 = bytes.fromhex('c117ea8ec828342f4dfb0ad6bd140e03a50720ece40169ee38bdc15d9eb64cf5')\n",
    "hash1 = bytes.fromhex('c131474164b412e3406696da1ee20ab0fc9bf41c8f05fa8ceea7a08d672d7cc5')\n",
    "parent = hash256(hash0 + hash1)\n",
    "print(parent.hex())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 1\n",
    "\n",
    "Write the `merkle_parent` function.\n",
    "\n",
    "#### Make [this test](/edit/code-ch11/helper.py) pass: `helper.py:HelperTest:test_merkle_parent`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 1\n",
    "\n",
    "reload(helper)\n",
    "run(helper.HelperTest(\"test_merkle_parent\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from helper import merkle_parent\n",
    "hex_hashes = [\n",
    "    'c117ea8ec828342f4dfb0ad6bd140e03a50720ece40169ee38bdc15d9eb64cf5',\n",
    "    'c131474164b412e3406696da1ee20ab0fc9bf41c8f05fa8ceea7a08d672d7cc5',\n",
    "    'f391da6ecfeed1814efae39e7fcb3838ae0b02c02ae7d0a5848a66947c0727b0',\n",
    "    '3d238a92a94532b946c90e19c49351c763696cff3db400485b813aecb8a13181',\n",
    "    '10092f2633be5f3ce349bf9ddbde36caa3dd10dfa0ec8106bce23acbff637dae',\n",
    "]\n",
    "hashes = [bytes.fromhex(x) for x in hex_hashes]\n",
    "if len(hashes) % 2 == 1:\n",
    "    hashes.append(hashes[-1])\n",
    "parent_level = []\n",
    "for i in range(0, len(hashes), 2):\n",
    "    parent = merkle_parent(hashes[i], hashes[i+1])\n",
    "    parent_level.append(parent)\n",
    "for item in parent_level:\n",
    "    print(item.hex())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 2\n",
    "\n",
    "Write the `merkle_parent_level` function.\n",
    "\n",
    "#### Make [this test](/edit/code-ch11/helper.py) pass: `helper.py:HelperTest:test_merkle_parent_level`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 2\n",
    "\n",
    "reload(helper)\n",
    "run(helper.HelperTest(\"test_merkle_parent_level\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from helper import merkle_parent_level\n",
    "hex_hashes = [\n",
    "    'c117ea8ec828342f4dfb0ad6bd140e03a50720ece40169ee38bdc15d9eb64cf5',\n",
    "    'c131474164b412e3406696da1ee20ab0fc9bf41c8f05fa8ceea7a08d672d7cc5',\n",
    "    'f391da6ecfeed1814efae39e7fcb3838ae0b02c02ae7d0a5848a66947c0727b0',\n",
    "    '3d238a92a94532b946c90e19c49351c763696cff3db400485b813aecb8a13181',\n",
    "    '10092f2633be5f3ce349bf9ddbde36caa3dd10dfa0ec8106bce23acbff637dae',\n",
    "    '7d37b3d54fa6a64869084bfd2e831309118b9e833610e6228adacdbd1b4ba161',\n",
    "    '8118a77e542892fe15ae3fc771a4abfd2f5d5d5997544c3487ac36b5c85170fc',\n",
    "    'dff6879848c2c9b62fe652720b8df5272093acfaa45a43cdb3696fe2466a3877',\n",
    "    'b825c0745f46ac58f7d3759e6dc535a1fec7820377f24d4c2c6ad2cc55c0cb59',\n",
    "    '95513952a04bd8992721e9b7e2937f1c04ba31e0469fbe615a78197f68f52b7c',\n",
    "    '2e6d722e5e4dbdf2447ddecc9f7dabb8e299bae921c99ad5b0184cd9eb8e5908',\n",
    "    'b13a750047bc0bdceb2473e5fe488c2596d7a7124b4e716fdd29b046ef99bbf0',\n",
    "]\n",
    "hashes = [bytes.fromhex(x) for x in hex_hashes]\n",
    "current_hashes = hashes\n",
    "while len(current_hashes) > 1:\n",
    "    current_hashes = merkle_parent_level(current_hashes)\n",
    "print(current_hashes[0].hex())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 3\n",
    "\n",
    "Write the `merkle_root` function.\n",
    "\n",
    "#### Make [this test](/edit/code-ch11/helper.py) pass: `helper.py:HelperTest:test_merkle_root`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 3\n",
    "\n",
    "reload(helper)\n",
    "run(helper.HelperTest(\"test_merkle_root\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from helper import merkle_root\n",
    "tx_hex_hashes = [\n",
    "    '42f6f52f17620653dcc909e58bb352e0bd4bd1381e2955d19c00959a22122b2e',\n",
    "    '94c3af34b9667bf787e1c6a0a009201589755d01d02fe2877cc69b929d2418d4',\n",
    "    '959428d7c48113cb9149d0566bde3d46e98cf028053c522b8fa8f735241aa953',\n",
    "    'a9f27b99d5d108dede755710d4a1ffa2c74af70b4ca71726fa57d68454e609a2',\n",
    "    '62af110031e29de1efcad103b3ad4bec7bdcf6cb9c9f4afdd586981795516577',\n",
    "    '766900590ece194667e9da2984018057512887110bf54fe0aa800157aec796ba',\n",
    "    'e8270fb475763bc8d855cfe45ed98060988c1bdcad2ffc8364f783c98999a208',\n",
    "]\n",
    "tx_hashes = [bytes.fromhex(x) for x in tx_hex_hashes]\n",
    "hashes = [h[::-1] for h in tx_hashes]\n",
    "print(merkle_root(hashes)[::-1].hex())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 4\n",
    "\n",
    "Write the `validate_merkle_root` method for `Block`.\n",
    "\n",
    "#### Make [this test](/edit/code-ch11/block.py) pass: `block.py:BlockTest:test_validate_merkle_root`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 4\n",
    "\n",
    "reload(block)\n",
    "run(block.BlockTest(\"test_validate_merkle_root\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "total = 16\n",
    "max_depth = math.ceil(math.log(total, 2))\n",
    "merkle_tree = []\n",
    "for depth in range(max_depth + 1):\n",
    "    num_items = math.ceil(total / 2**(max_depth - depth))\n",
    "    level_hashes = [None] * num_items\n",
    "    merkle_tree.append(level_hashes)\n",
    "for level in merkle_tree:\n",
    "    print(level)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 5\n",
    "\n",
    "Create an empty Merkle Tree with 27 items and print each level."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 5\n",
    "\n",
    "import math\n",
    "\n",
    "total = 27\n",
    "# use math.ceil(math.log(total, 2)) to get the max depth\n",
    "# create an array of arrays for the tree\n",
    "# loop through all possible depths\n",
    "    # get how many items at this depth\n",
    "    # use math.ceil(total / 2**(max depth - current depth))\n",
    "    # create an empty array for this level\n",
    "    # append the level to the tree\n",
    "# print the tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from merkleblock import MerkleTree\n",
    "from helper import merkle_parent_level\n",
    "hex_hashes = [\n",
    "    \"9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb\",\n",
    "    \"5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b\",\n",
    "    \"82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05\",\n",
    "    \"507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308\",\n",
    "    \"a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330\",\n",
    "    \"bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add\",\n",
    "    \"ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836\",\n",
    "    \"457743861de496c429912558a106b810b0507975a49773228aa788df40730d41\",\n",
    "    \"7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a\",\n",
    "    \"b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9\",\n",
    "    \"9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab\",\n",
    "    \"b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638\",\n",
    "    \"b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263\",\n",
    "    \"c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800\",\n",
    "    \"c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2\",\n",
    "    \"f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e\",\n",
    "]\n",
    "tree = MerkleTree(len(hex_hashes))\n",
    "tree.nodes[4] = [bytes.fromhex(h) for h in hex_hashes]\n",
    "tree.nodes[3] = merkle_parent_level(tree.nodes[4])\n",
    "tree.nodes[2] = merkle_parent_level(tree.nodes[3])\n",
    "tree.nodes[1] = merkle_parent_level(tree.nodes[2])\n",
    "tree.nodes[0] = merkle_parent_level(tree.nodes[1])\n",
    "print(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from merkleblock import MerkleTree\n",
    "from helper import merkle_parent\n",
    "hex_hashes = [\n",
    "    \"9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb\",\n",
    "    \"5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b\",\n",
    "    \"82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05\",\n",
    "    \"507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308\",\n",
    "    \"a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330\",\n",
    "    \"bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add\",\n",
    "    \"ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836\",\n",
    "    \"457743861de496c429912558a106b810b0507975a49773228aa788df40730d41\",\n",
    "    \"7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a\",\n",
    "    \"b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9\",\n",
    "    \"9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab\",\n",
    "    \"b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638\",\n",
    "    \"b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263\",\n",
    "    \"c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800\",\n",
    "    \"c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2\",\n",
    "    \"f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e\",\n",
    "]\n",
    "tree = MerkleTree(len(hex_hashes))\n",
    "tree.nodes[4] = [bytes.fromhex(h) for h in hex_hashes]\n",
    "while tree.root() is None:\n",
    "    if tree.is_leaf():\n",
    "        tree.up()\n",
    "    else:\n",
    "        left_hash = tree.get_left_node()\n",
    "        right_hash = tree.get_right_node()\n",
    "        if left_hash is None:\n",
    "            tree.left()\n",
    "        elif right_hash is None:\n",
    "            tree.right()\n",
    "        else:\n",
    "            tree.set_current_node(merkle_parent(left_hash, right_hash))\n",
    "            tree.up()\n",
    "print(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from merkleblock import MerkleTree\n",
    "from helper import merkle_parent\n",
    "hex_hashes = [\n",
    "    \"9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb\",\n",
    "    \"5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b\",\n",
    "    \"82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05\",\n",
    "    \"507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308\",\n",
    "    \"a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330\",\n",
    "    \"bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add\",\n",
    "    \"ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836\",\n",
    "    \"457743861de496c429912558a106b810b0507975a49773228aa788df40730d41\",\n",
    "    \"7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a\",\n",
    "    \"b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9\",\n",
    "    \"9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab\",\n",
    "    \"b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638\",\n",
    "    \"b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263\",\n",
    "    \"c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800\",\n",
    "    \"c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2\",\n",
    "    \"f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e\",\n",
    "    \"38faf8c811988dff0a7e6080b1771c97bcc0801c64d9068cffb85e6e7aacaf51\",\n",
    "]\n",
    "tree = MerkleTree(len(hex_hashes))\n",
    "tree.nodes[5] = [bytes.fromhex(h) for h in hex_hashes]\n",
    "while tree.root() is None:\n",
    "    if tree.is_leaf():\n",
    "        tree.up()\n",
    "    else:\n",
    "        left_hash = tree.get_left_node()\n",
    "        if left_hash is None:\n",
    "            tree.left()\n",
    "        elif tree.right_exists():\n",
    "            right_hash = tree.get_right_node()\n",
    "            if right_hash is None:\n",
    "                tree.right()\n",
    "            else:\n",
    "                tree.set_current_node(merkle_parent(left_hash, right_hash))\n",
    "                tree.up()\n",
    "        else:\n",
    "            tree.set_current_node(merkle_parent(left_hash, left_hash))\n",
    "            tree.up()\n",
    "print(tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 6\n",
    "\n",
    "Write the `parse` method for `MerkleBlock`.\n",
    "\n",
    "#### Make [this test](/edit/code-ch11/merkleblock.py) pass: `merkleblock.py:MerkleBlockTest:test_parse`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 6\n",
    "\n",
    "reload(merkleblock)\n",
    "run(merkleblock.MerkleBlockTest(\"test_parse\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise 7\n",
    "\n",
    "Write the `is_valid` method for `MerkleBlock`\n",
    "\n",
    "#### Make [this test](/edit/code-ch11/merkleblock.py) pass: `merkleblock.py:MerkleBlockTest:test_is_valid`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercise 7\n",
    "\n",
    "reload(merkleblock)\n",
    "run(merkleblock.MerkleBlockTest(\"test_is_valid\"))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
